package chapter03_binaryTree;

import java.util.Stack;

/**
 * 描述：
 *      返回二叉搜索树中两个错误的结点
 *      在错误的二叉树进行中序遍历后，如果是正常的搜索二叉树，那么遍历的过程就是圣墟队列，
 *      但是如果有两个错误的结点，那么就会出现一次或者两次降序
 *      如果出现两次降序，那么第一次降序时的较大的结点是第一个错误结点，第二次降序时较小的结点是第二个错误的结点。
 *              判断的标准是如何将两个错误的结点调换后能够维持升序
 *      如果出现一次降序，那么第一个错误的结点就是第一次降序时较大的结点，第二个错误的结点就是第一次降序时较小的结点
 * @author hl
 * @date 2021/5/17 20:40
 */
public class GetTwoErrNodes {
    public static void main(String[] args) {
        SerialBinaryTree serialBinaryTree = new SerialBinaryTree();
        Node head = serialBinaryTree.reconByLevel("2!5!4!1!3!#!#!#!#!#!#!");
        GetTwoErrNodes getTwoErrNodes = new GetTwoErrNodes();
        PrintTree printTree = new PrintTree();
        printTree.printTree(head);
        System.out.println("========================================================");
        Node recoverTree = getTwoErrNodes.recoverTree(head);
        printTree.printTree(recoverTree);
    }
    

    int index = 0;
    Node[] errNodes = new Node[2];
    boolean isFirst = true;
    public Node[] getTwoErrNodes2(Node head){
        process(head, null);
        return errNodes;
    }
    public void process(Node head, Node pre){
        if (head == null) {
            return ;
        }
        process(head.left , pre);
        if (pre != null && pre.val > head.val) {
            if (isFirst) {
                errNodes[0] = pre;
                errNodes[1] = head;
            }else{
                errNodes[1] = head;
            }
            isFirst = !isFirst;
        }
        pre = head;
        process(head.right, pre);
    }
    //========================================


    public Node[] getTwoErrNodes(Node head){
        if (head == null) {
            return new Node[2];
        }
        Stack<Node> stack = new Stack<>();
        Node[] errNodes = new Node[2];
        Node cur = head;
        Node pre = null;
        while(!stack.isEmpty() || cur != null){
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                if (pre != null && pre.val > cur.val) {
                    errNodes[0] = errNodes[0] == null ? pre : errNodes[0];
                    errNodes[1] = cur;
                }
                pre = cur;
                cur = cur.right;
            }
        }
        return errNodes;
    }

    /**
     * 进阶：找到两个错误的结点后，在结构上完全交换两个结点，重新调整为搜索二叉树
     * 调整结构主要考虑三种组合情况：
     *      1）交换后结点是否会成为头结点
     *      2）交换的结点是否为父子结点关系
     *      3）交换的结点是父节点的左孩子还是右孩子
     * @param head
     * @return
     */
    public Node recoverTree(Node head){
        Node[] errs = getTwoErrNodes(head);
        Node[] parents = getTwoErrParents(head, errs[0], errs[1]);
        Node e1 = errs[0];
        Node e2 = errs[1];
        Node e1P = parents[0];
        Node e2P = parents[0];
        Node e1L = errs[0].left;
        Node e1R = errs[0].right;
        Node e2L = errs[1].left;
        Node e2R = errs[1].right;
        Node temp = null;
        Node p = null;
        if (e1 == head) {
            if (e2 == e1R) {
                temp = e1.left;
                e1.left = e2.left;
                e2.left = temp;
                e1.right = e2.right;
                e2.right = e1;
            }else{
                temp = e1.left;
                e1.left = e2.left;
                e2.left = temp;
                temp = e2.right;
                e2.right = e1.right;
                e1.right = temp;
                if (e2P.left == e2) {
                    e2P.left = e1;
                }else{
                    e2P.right = e1;
                }
            }
            head = e2;
        }else if (e2 == head) {
            if (e1 == e2L) {
                temp = e1.right;
                e1.right = e2.right;
                e2.right = temp;
                e2.left = e1.left;
                e1.left = e2;
            }else{
                temp = e1.right;
                e1.right = e2.right;
                e2.right = temp;
                temp = e2.left;
                e2.left = e1.left;
                e1.left = temp;
                if (e1P.left == e1) {
                    e1P.left = e2;
                }else{
                    e1P.right = e2;
                }
            }
            head = e1;
        }else{
            if (e1 == e2L) {
                temp = e1.right;
                e1.right = e2.right;
                e2.right = temp;
                e2.left = e1.left;
                e1.left = e2;
                if (e2P.left == e2) {
                    e2P.left = e1;
                }else{
                    e2P.right = e1;
                }
            }else if (e2 == e1R) {
                temp = e1.left;
                e1.left = e2.left;
                e2.left = temp;
                e1.right = e2.right;
                e2.right = e1;
                if (e1P.left == e1) {
                    e1P.left = e2;
                }else{
                    e1P.right = e2;
                }
            }else{
                temp = e1.right;
                e1.right = e2.right;
                e2.right = temp;
                temp = e2.left;
                e2.left = e1.left;
                e1.left = temp;
                if (e1P.left == e1 && e2P.left == e2) {
                    e1P.left = e2;
                    e2P.left = e1;
                }else if(e1P.left == e1 && e2P.right == e2){
                    e1P.left = e2;
                    e2P.right = e1;
                }else if (e1P.right == e1 && e2P.left == e2) {
                    e1P.right = e2;
                    e2P.left = e1;
                }else if (e1P.right == e1 && e2P.right == e2) {
                    e1P.right = e2;
                    e2P.right = e1;
                }
            }
        }
        return head;
    }

    public Node[] getTwoErrParents(Node head, Node e1, Node e2){
        Node[] errParents = new Node[2];
        Stack<Node> stack = new Stack<>();
        while(!stack.isEmpty() || head != null){
            if (head != null) {
                stack.push(head);
                head = head.left;
            }else{
                head = stack.pop();
                if (head.left == e1 || head.right == e1) {
                    errParents[0] = head;
                }
                if (head.left == e2 || head.right == e2) {
                    errParents[1] = head;
                }
                head = head.right;
            }
        }
        return errParents;
    }
}
